/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mvp.algorithms.unions;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 *
 * @author WORKSPOT2
 */
public class QuickUnionChecker
{

    private int id[];
    private double border;

    public QuickUnionChecker(int numberOfObjects)
    {
        this.id = new int[numberOfObjects];
        this.border = (Math.log(numberOfObjects) / Math.log(2));
    }

    public boolean checkString(String arrayStr)
    {
        StringTokenizer tokenizer = new StringTokenizer(arrayStr, " ");
        int i = 0;
        while (tokenizer.hasMoreTokens())
        {
            id[i] = Integer.parseInt(tokenizer.nextToken());
            i++;
        }
        int tmpRoot;
        for (int j = 0; j < id.length; j++)
        {
            tmpRoot = getRoot(j);
            if (tmpRoot < 0)
            {
                return false;
            }
        }
        buildTree();
        return true;
    }

    private int getRoot(int i)
    {
        int counter = 0;
        while (i != id[i])
        {
            i = id[i];
            counter++;
            if (counter > border)
            {
                return -1;
            }
        }
        return i;
    }

    private void buildTree()
    {
        List<LinkedList<Integer>> branches = new ArrayList<LinkedList<Integer>>();
        LinkedList<Integer> tmp;
        for (int i = 0; i < id.length; i++)
        {
            tmp = new LinkedList<Integer>();
            fillBranch(tmp, i);
            branches.add(tmp);
        }
        showBranches(branches);
    }

    private void fillBranch(LinkedList<Integer> branch, int i)
    {
        while (i != id[i])
        {
            branch.add(i);
            i = id[i];
        }
        branch.add(i);
    }

    private void showBranches(List<LinkedList<Integer>> branches)
    {
        Iterator<LinkedList<Integer>> iter = branches.iterator();
        LinkedList<Integer> tmp;
        Iterator<Integer> deepIter;
        while (iter.hasNext())
        {
            tmp = iter.next();
            deepIter = tmp.iterator();
            while(deepIter.hasNext())
            {
                System.out.print(deepIter.next()+"-");
            }
            System.out.println();
        }
    }
}
